package com.nowcoder.面试必刷101;

import java.util.HashMap;

/**
 * @Description: 设计LRU缓存结构
 * @author： yeswater
 * @create： 2024/6/14
 */

public class BM100 {
	
	public static void main(String[] args) {
		BM100 LRU = new BM100(2);
		LRU.set(1, 1);
		LRU.set(2, 2);
		LRU.get(1);
		LRU.set(3, 3);
		LRU.get(2);
		LRU.set(4, 4);
		LRU.get(1);
		LRU.get(3);
		LRU.get(4);
	}
	
	class Node {
		int key;
		int val;
		Node pre;
		Node next;
		
		public Node(int key, int val, Node head, Node tail) {
			this.key = key;
			this.val = val;
			this.pre = head;
			this.next = tail;
		}
	}
	
	private final int capacity;
	
	private int curLen; // 缓存当前长度
	
	private final HashMap<Integer, Node> map;
	
	private Node head ;
	
	private Node tail ;
	
	public BM100(int capacity) {
		this.capacity = capacity;
		this.head = null;
		this.tail = null;
		this.curLen = 0;
		map = new HashMap<Integer, Node>(capacity);
		System.out.println("==>capacity:" + capacity);
	}
	
	public int get(int key) {
		if (!map.containsKey(key)) return -1;
		else {
			Node node = map.get(key);
			if (head != node) markRecently(node);
			return map.get(key).val;
		}
	}
	
	//exist and update cache
	private void markRecently(Node node) {
		if (node == tail) {
			tail = tail.pre;
			tail.next = null;
		} else {
			node.pre.next = node.next;
			node.next.pre = node.pre;
		}
		head.pre = node;
		node.next = head;
		head = node;
	}
	
	public void set(int key, int value) {
		// already exist
		if (map.containsKey(key)) {
			Node node = map.get(key);
			if (node != head) {
				node.val = value;
				markRecently(node);
			} else {
				node.val = value;
			}
		} else {
			// not exist
			if (head == null) {
				// not exist and blank
				head = new Node(key, value, null, null);
				tail = head;
			} else {
				// not exist and update cache
				Node node = new Node(key, value, null, head);
				head.pre = node;
				head = node;
			}
			curLen++;
			map.put(key, head);
			// check cache space
			if (curLen > capacity) {
				map.remove(tail.key);
				tail = tail.pre;
				tail.next = null;
				curLen--;
			}
		}
	}
}
